package leetcode.weekly.week295;

import java.util.LinkedList;
import java.util.Queue;

//Solution4Test
public class Solution4 {

	// Solution4Test
	public int minimumObstacles(int[][] grid) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0 });
		int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };
		int m = grid.length, n = grid[0].length;
		int ans = grid[0][0] + grid[m - 1][n - 1];
		grid[0][0] = -1;
		grid[m - 1][n - 1] = -1;
		while (true) {
			Queue<int[]> block = new LinkedList<>();
			while (!queue.isEmpty()) {
				int[] cur = queue.poll();
				int x = cur[0], y = cur[1];
				for (int i = 0; i < 8; i += 2) {
					int nextx = x + d[i], nexty = y + d[i + 1];
					if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
						if (nextx == m - 1 && nexty == n - 1) {
							return ans;
						}
						if (grid[nextx][nexty] == 0) {
							queue.add(new int[] { nextx, nexty });
							grid[nextx][nexty] = -1;
						}
						if (grid[nextx][nexty] == 1) {
							block.add(new int[] { nextx, nexty });
							grid[nextx][nexty] = -1;
						}
					}
				}
			}
			queue = block;
			ans++;
		}
	}

}
